{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Put Boxes Into the Warehouse II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxBoxesInWarehouse"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #把箱子放进仓库里 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定两个正整数数组 <code>boxes</code> 和 <code>warehouse</code> ，分别包含单位宽度的箱子的高度，以及仓库中<code>n</code>个房间各自的高度。仓库的房间分别从<code>0</code> 到 <code>n - 1</code>自左向右编号，<code>warehouse[i]</code>（索引从 0 开始）是第 <code>i</code> 个房间的高度。</p>\n",
    "\n",
    "<p>箱子放进仓库时遵循下列规则：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>箱子不可叠放。</li>\n",
    "\t<li>你可以重新调整箱子的顺序。</li>\n",
    "\t<li>箱子可以从任意方向（左边或右边）推入仓库中。</li>\n",
    "\t<li>如果仓库中某房间的高度小于某箱子的高度，则这个箱子和之后的箱子都会停在这个房间的前面。</li>\n",
    "</ul>\n",
    "\n",
    "<p>你最多可以在仓库中放进多少个箱子？</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/08/30/22.png\" style=\"width: 401px; height: 202px;\" />\n",
    "<pre>\n",
    "<strong>输入:</strong> boxes = [1,2,2,3,4], warehouse = [3,4,1,2]\n",
    "<strong>输出:</strong> 4\n",
    "<strong>解释:\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/08/30/22-1.png\" style=\"width: 240px; height: 202px;\" />\n",
    "</strong>我们可以按如下顺序推入箱子:\n",
    "1- 从左边或右边把黄色箱子推入2号房间；\n",
    "2- 从右边把橙色箱子推入3号房间；\n",
    "3- 从左边把绿色箱子推入1号房间；\n",
    "4- 从左边把红色箱子推入0号房间；\n",
    "还有其他方式推入4个箱子，比如交换红色与绿色箱子，或者交换红色与橙色箱子。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/08/30/22-2.png\" style=\"width: 401px; height: 242px;\" />\n",
    "<pre>\n",
    "<strong>输入:</strong> boxes = [3,5,5,2], warehouse = [2,1,3,4,5]\n",
    "<strong>输出:</strong> 3\n",
    "<strong>解释:\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/08/30/22-3.png\" style=\"width: 280px; height: 242px;\" />\n",
    "</strong>因为只有一个高度大于等于5的房间，所以无法将两个高度为5的箱子都推入仓库。\n",
    "还有其他方式推入箱子，比如将绿色箱子推入2号房间，或者在绿色及红色箱子之前将橙色箱子推入2号房间。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> boxes = [1,2,3], warehouse = [1,2,3,4]\n",
    "<strong>输出:</strong> 3\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> boxes = [4,5,6], warehouse = [3,3,3,3,3]\n",
    "<strong>输出:</strong> 0\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == warehouse.length</code></li>\n",
    "\t<li><code>1 <= boxes.length, warehouse.length <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 <= boxes[i], warehouse[i] <= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [put-boxes-into-the-warehouse-ii](https://leetcode.cn/problems/put-boxes-into-the-warehouse-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [put-boxes-into-the-warehouse-ii](https://leetcode.cn/problems/put-boxes-into-the-warehouse-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,2,3,4]\\n[3,4,1,2]', '[3,5,5,2]\\n[2,1,3,4,5]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxBoxesInWarehouse(self, boxes: List[int], warehouse: List[int]) -> int:\n",
    "        mn = inf\n",
    "        n = len(warehouse)\n",
    "        for i in range(n):\n",
    "            mn = min(mn, warehouse[i])\n",
    "            warehouse[i] = mn\n",
    "        boxes.sort(reverse=True)\n",
    "        ans = 0\n",
    "        while boxes and warehouse:\n",
    "            if boxes[-1] <= warehouse[-1]:\n",
    "                boxes.pop()\n",
    "                ans += 1\n",
    "            warehouse.pop()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxBoxesInWarehouse(self, boxes: List[int], warehouse: List[int]) -> int:\n",
    "        s = warehouse[0]\n",
    "        for i in range(1, len(warehouse)):\n",
    "            if warehouse[i] > s:\n",
    "                warehouse[i] = s\n",
    "            s = min(s, warehouse[i])\n",
    "        boxes.sort()\n",
    "        n = len(boxes)\n",
    "        i = ans = 0\n",
    "        while i < n:\n",
    "            while warehouse and warehouse[-1] < boxes[i]:\n",
    "                warehouse.pop()\n",
    "            if not warehouse:\n",
    "                break\n",
    "            warehouse.pop()\n",
    "            ans += 1\n",
    "            i += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 动态规划+堆（优先队列）\n",
    "    # https://leetcode.cn/problems/put-boxes-into-the-warehouse-i/solutions/2392550/ba-xiang-zi-fang-jin-cang-ku-li-i-by-lee-kpx5/\n",
    "    def maxBoxesInWarehouse(self, boxes: List[int], warehouse: List[int]) -> int:\n",
    "        n = len(warehouse)\n",
    "        for i in range(1, n):\n",
    "            warehouse[i] = warehouse[i-1] if warehouse[i-1] < warehouse[i] else warehouse[i]\n",
    "\n",
    "        heapq.heapify(boxes)\n",
    "        ans = 0\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if boxes and boxes[0] <= warehouse[i]:\n",
    "                ans += 1\n",
    "                heapq.heappop(boxes)\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxBoxesInWarehouse(self, boxes: List[int], warehouse: List[int]) -> int:\n",
    "        boxes.sort()\n",
    "        for i in range(1, len(warehouse)):\n",
    "            warehouse[i] = min(warehouse[i - 1], warehouse[i])\n",
    "        res = 0\n",
    "        right = len(warehouse) - 1\n",
    "        i = 0\n",
    "        while right >= 0 and res < len(boxes):\n",
    "            if boxes[i] <= warehouse[right]:\n",
    "                res += 1\n",
    "                i += 1\n",
    "                right -= 1\n",
    "            else:\n",
    "                right -= 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxBoxesInWarehouse(self, boxes: List[int], warehouse: List[int]) -> int:\n",
    "        m, n = len(boxes), len(warehouse)\n",
    "        boxes.sort()\n",
    "        ans = 0\n",
    "        for i in range(1, n):\n",
    "            warehouse[i] = min(warehouse[i], warehouse[i - 1])\n",
    "        for h in reversed(warehouse):\n",
    "            if ans < m and h >= boxes[ans]:\n",
    "                ans += 1\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxBoxesInWarehouse(self, boxes: List[int], warehouse: List[int]) -> int:\n",
    "        n = len(warehouse)\n",
    "\n",
    "        min_so_far = math.inf\n",
    "        for i in range(n):\n",
    "            warehouse[i] = min(min_so_far, warehouse[i])\n",
    "            min_so_far = min(min_so_far, warehouse[i])\n",
    "\n",
    "        boxes = sorted(boxes)\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if res < len(boxes) and boxes[res] <= warehouse[i]:\n",
    "                res += 1\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "   def maxBoxesInWarehouse(self, boxes: List[int], warehouse: List[int]) -> int:\n",
    "       # 对仓库房间的高度进行预处理，以获得可用高度\n",
    "       for i in range(1, len(warehouse)):\n",
    "           warehouse[i] = min(warehouse[i - 1], warehouse[i])\n",
    "\n",
    "       # 从最小到最大遍历方框\n",
    "       boxes.sort()\n",
    "\n",
    "       count = 0\n",
    "\n",
    "       for room in reversed(warehouse):\n",
    "           # 清点能放进当前库房的箱子\n",
    "           if count < len(boxes) and boxes[count] <= room:\n",
    "               count += 1\n",
    "\n",
    "       return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxBoxesInWarehouse(self, B: List[int], H: List[int]) -> int:\n",
    "        lo = inf\n",
    "        for i, h in enumerate(H):\n",
    "            if lo > h: lo = h\n",
    "            H[i] = lo\n",
    "        \n",
    "        B.sort()\n",
    "        i, m = 0, len(B)\n",
    "        for h in reversed(H):\n",
    "            if i < m and B[i] <= h:\n",
    "                i += 1\n",
    "        return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxBoxesInWarehouse(self, boxes: List[int], warehouse: List[int]) -> int:\n",
    "        i, j = len(boxes) - 1, len(warehouse) - 1\n",
    "        boxes.sort(reverse=True)\n",
    "        ans = 0\n",
    "        mn = warehouse[0]\n",
    "        for idx in range(len(warehouse)):\n",
    "            if mn < warehouse[idx]:\n",
    "                warehouse[idx] = mn\n",
    "            elif mn > warehouse[idx]:\n",
    "                mn = warehouse[idx]\n",
    "\n",
    "        while i >= 0 and j >= 0:\n",
    "            if boxes[i] <= warehouse[j]:\n",
    "                ans += 1\n",
    "                i -= 1\n",
    "                j -= 1\n",
    "            elif boxes[i] > warehouse[j]:\n",
    "                j -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def maxBoxesInWarehouse(self, boxes: List[int], warehouse: List[int]) -> int:\n",
    "        n = len(warehouse)\n",
    "\n",
    "        min_so_far = math.inf\n",
    "        for i in range(n):\n",
    "            warehouse[i] = min(min_so_far, warehouse[i])\n",
    "            min_so_far = min(min_so_far, warehouse[i])\n",
    "\n",
    "        boxes = SortedList(boxes)\n",
    "        \n",
    "        res = 0\n",
    "\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            limit = warehouse[i]\n",
    "            pos = boxes.bisect_right(limit)\n",
    "            if pos != 0:\n",
    "                res += 1\n",
    "                boxes.remove(boxes[pos - 1])\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxBoxesInWarehouse(self, B: List[int], H: List[int]) -> int:\n",
    "        lo = inf\n",
    "        for i, h in enumerate(H):\n",
    "            if lo > h: lo = h\n",
    "            H[i] = lo\n",
    "        \n",
    "        B.sort()\n",
    "        i, m = 0, len(B)\n",
    "        for h in H[::-1]:\n",
    "            if i < m and B[i] <= h:\n",
    "                i += 1\n",
    "        return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxBoxesInWarehouse(self, boxes: List[int], warehouse: List[int]) -> int:\n",
    "        warehouse = list(accumulate(warehouse, func=min))\n",
    "        # print(warehouse)\n",
    "        boxes.sort()\n",
    "        box_id = ans = 0\n",
    "        n = len(boxes)\n",
    "        for height in reversed(warehouse):\n",
    "            if box_id == n:\n",
    "                return n\n",
    "            if height >= boxes[box_id]:\n",
    "                box_id += 1\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxBoxesInWarehouse(self, boxes: List[int], warehouse: List[int]) -> int:\n",
    "        box_len = len(boxes)\n",
    "        house_len = len(warehouse)\n",
    "        ave_house = [0 for _ in range(house_len)]\n",
    "        ave_h = float('inf')\n",
    "        for i in range(house_len):\n",
    "            if ave_h > warehouse[i]:\n",
    "                ave_h = warehouse[i]\n",
    "            ave_house[i] = ave_h\n",
    "        boxes.sort()\n",
    "        b_i = 0\n",
    "        for i in range(house_len - 1, -1, -1):\n",
    "            if boxes[b_i] <= ave_house[i]:\n",
    "                b_i += 1\n",
    "            if b_i >= box_len:\n",
    "                break\n",
    "            else:\n",
    "                continue\n",
    "        return b_i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxBoxesInWarehouse(self, boxes: List[int], warehouse: List[int]) -> int:\n",
    "        m, n = len(boxes), len(warehouse)\n",
    "        boxes.sort(reverse=True)\n",
    "        if m > n:\n",
    "            boxes = boxes[m - n:]\n",
    "            m = n \n",
    "        low, high = 0, m \n",
    "\n",
    "        def check(x):\n",
    "            for i in range(x):\n",
    "                if boxes[i + m - x] > warehouse[i]:\n",
    "                    return False\n",
    "            return True \n",
    "        \n",
    "        ans = 0\n",
    "        while low <= high:\n",
    "            mid = (low + high) // 2\n",
    "            if check(mid):\n",
    "                ans = mid \n",
    "                low = mid + 1\n",
    "            else:\n",
    "                high = mid - 1\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "   def maxBoxesInWarehouse(self, boxes: List[int], warehouse: List[int]) -> int:\n",
    "\n",
    "       i = 0\n",
    "       count = 0\n",
    "       boxes.sort(reverse = True)\n",
    "\n",
    "       for room in warehouse:\n",
    "           # 从最小到最大遍历方框\n",
    "           # 丢弃不适合当前仓库的箱子\n",
    "           while i < len(boxes) and boxes[i] > room:\n",
    "               i += 1\n",
    "           if i == len(boxes):\n",
    "               return count\n",
    "           count += 1\n",
    "           i += 1\n",
    "\n",
    "       return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxBoxesInWarehouse(self, boxes: List[int], warehouse: List[int]) -> int:\n",
    "        m, n = len(boxes), len(warehouse)\n",
    "        mi = min(warehouse)\n",
    "        mi_idx = warehouse.index(mi)\n",
    "        l, r = mi_idx, mi_idx + 1\n",
    "        for i in range(1, mi_idx):\n",
    "            warehouse[i] = min(warehouse[i - 1], warehouse[i])\n",
    "        for j in range(n - 2, mi_idx, -1):\n",
    "            warehouse[j] = min(warehouse[j], warehouse[j + 1])\n",
    "        boxes.sort()\n",
    "        ans = 0\n",
    "        while 1:\n",
    "            if ans == m:\n",
    "                break\n",
    "            while l >= 0 and warehouse[l] < boxes[ans]:\n",
    "                l -= 1\n",
    "            # if l < 0:\n",
    "            #     break\n",
    "            while r <= n - 1 and warehouse[r] < boxes[ans]:\n",
    "                r += 1\n",
    "            # if r >= n:\n",
    "            #     break\n",
    "            if l < 0 and r > n - 1:\n",
    "                break\n",
    "            if l < 0:\n",
    "                r += 1\n",
    "                ans += 1\n",
    "            elif r > n - 1:\n",
    "                l -= 1\n",
    "                ans += 1\n",
    "            else:\n",
    "                mi_tmp = min(warehouse[l], warehouse[r])\n",
    "                if mi_tmp == warehouse[l]:\n",
    "                    l -= 1\n",
    "                else:\n",
    "                    r += 1\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxBoxesInWarehouse(self, B: List[int], H: List[int]) -> int:\n",
    "        lo = min(H)\n",
    "        li = H.index(lo)\n",
    "        for i in range(1, li):\n",
    "            if H[i] > H[i - 1]: H[i] = H[i - 1]\n",
    "        for i in range(len(H) - 2, li, -1):\n",
    "            if H[i] > H[i + 1]: H[i] = H[i + 1]\n",
    "        # print(H)\n",
    "\n",
    "        H.sort()\n",
    "        B.sort()\n",
    "        i = 0\n",
    "        \n",
    "        for h in H:\n",
    "            if i < len(B) and B[i] <= h:\n",
    "                i += 1\n",
    "        return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxBoxesInWarehouse(self, boxes: List[int], warehouse: List[int]) -> int:\n",
    "        minIndex = 0\n",
    "        minVal = warehouse[0]\n",
    "        \n",
    "        n = len(boxes)\n",
    "        m = len(warehouse)\n",
    "        \n",
    "        maxFromLeft = [warehouse[x] for x in range(m)]\n",
    "        maxFromRight = [warehouse[x] for x in range(m)]\n",
    "        for i in range(1, m):\n",
    "            maxFromLeft[i] = min(maxFromLeft[i-1], maxFromLeft[i])\n",
    "        for i in range(m-2, -1 , -1):\n",
    "            maxFromRight[i] = min(maxFromRight[i+1], maxFromRight[i])\n",
    "\n",
    "        for i in range(m):\n",
    "            warehouse[i] = max(maxFromLeft[i], maxFromRight[i])\n",
    "        # print(maxFromLeft, maxFromRight)\n",
    "        for i in range(m):\n",
    "            if warehouse[i] < minVal:\n",
    "                minVal=warehouse[i]\n",
    "                minIndex=i\n",
    "        leftPtr, rightPtr = minIndex, minIndex\n",
    "        # print(leftPtr, rightPtr)\n",
    "        boxes.sort()\n",
    "        ret = 0\n",
    "        for item in boxes:\n",
    "            while leftPtr>=0 and item > warehouse[leftPtr]:\n",
    "                leftPtr-=1\n",
    "            while rightPtr<m and item > warehouse[rightPtr]:\n",
    "                rightPtr+=1\n",
    "            if leftPtr < 0 and rightPtr == m:\n",
    "                return ret\n",
    "            else:\n",
    "                ret+=1\n",
    "                if leftPtr == rightPtr:\n",
    "                    leftPtr-=1\n",
    "                    rightPtr+=1\n",
    "                elif leftPtr<0:\n",
    "                    rightPtr+=1\n",
    "                elif rightPtr == m:\n",
    "                    leftPtr-=1\n",
    "                else:\n",
    "                    if warehouse[leftPtr] <= warehouse[rightPtr]:\n",
    "                        leftPtr-=1\n",
    "                    else:\n",
    "                        rightPtr+=1\n",
    "            # print(item, leftPtr, rightPtr)\n",
    "        return ret "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def maxBoxesInWarehouse(self, boxes: List[int], warehouse: List[int]) -> int:\n",
    "        n = len(warehouse)\n",
    "        \n",
    "        # 修正仓库高度\n",
    "        min_idx = warehouse.index(min(warehouse))\n",
    "        for i in range(1, min_idx):\n",
    "            if warehouse[i] > warehouse[i-1]:\n",
    "                warehouse[i] = warehouse[i-1]\n",
    "        for i in range(n-2, min_idx, -1):\n",
    "            if warehouse[i] > warehouse[i+1]:\n",
    "                warehouse[i] = warehouse[i+1]\n",
    "        \n",
    "        # 排序箱子高度\n",
    "        boxes.sort(reverse=True)\n",
    "        \n",
    "        # 装箱子\n",
    "        pl, pr, pb, ans = 0, n-1, 0, 0\n",
    "        while pb < len(boxes) and pl <= pr:\n",
    "            left, right, box = warehouse[pl], warehouse[pr], boxes[pb]\n",
    "            if right >= left and right >= box:\n",
    "                ans += 1\n",
    "                pb += 1\n",
    "                pr -= 1\n",
    "            elif left > right and left >= box:\n",
    "                ans += 1\n",
    "                pb += 1\n",
    "                pl += 1\n",
    "            else:\n",
    "                pb += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxBoxesInWarehouse(self, boxes: List[int], warehouse: List[int]) -> int:\n",
    "        boxes.sort(reverse=True) # 从小到大排序 然后呢 我们怎么处理这个 排序贪心 如何贪心呢\n",
    "        n, m = len(warehouse), len(boxes)\n",
    "        sub = [0 for _ in range(n)]\n",
    "        sub[-1] = warehouse[-1]\n",
    "        pre = [0 for _ in range(n)]\n",
    "        pre[0] = warehouse[0]\n",
    "        for i in range(n-2, -1, -1):\n",
    "            sub[i] = min(sub[i+1], warehouse[i])\n",
    "        for i in range(1, n):\n",
    "            pre[i] = min(pre[i-1], warehouse[i])\n",
    "        data = []\n",
    "        for a, b in zip(sub, pre):\n",
    "            data.append(a if a > b else b)\n",
    "        \n",
    "        data.sort(reverse=True)\n",
    "        # print(data)\n",
    "        # print(boxes)\n",
    "        index = ans = 0\n",
    "        for i in range(m):\n",
    "            # print(data[i])\n",
    "            # print(boxes[index])\n",
    "            if boxes[i] <= data[index]:\n",
    "                index += 1\n",
    "                ans += 1\n",
    "            # else:\n",
    "            if index == n:\n",
    "                break\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxBoxesInWarehouse(self, boxes: List[int], warehouse: List[int]) -> int:\n",
    "        h_n = len(warehouse)\n",
    "        L2R = [0 for _ in range(h_n)]\n",
    "        ceil = float('inf')\n",
    "        for i in range(h_n):\n",
    "            if ceil > warehouse[i]:\n",
    "                ceil = warehouse[i]\n",
    "            L2R[i] = ceil\n",
    "        R2L = [0 for _ in range(h_n)]\n",
    "        ceil = float('inf')\n",
    "        for i in range(h_n - 1, -1, -1):\n",
    "            if ceil > warehouse[i]:\n",
    "                ceil = warehouse[i]\n",
    "            R2L[i] = ceil\n",
    "        max_avail_h = [0 for _ in range(h_n)]\n",
    "        for i in range(h_n):\n",
    "            max_avail_h[i] = min(warehouse[i], max(L2R[i], R2L[i]))\n",
    "        max_avail_h.sort()\n",
    "        boxes.sort()\n",
    "        b_i = 0\n",
    "        for i in range(h_n):\n",
    "            if boxes[b_i] <= max_avail_h[i]:\n",
    "                b_i += 1\n",
    "            if b_i >= len(boxes):\n",
    "                break\n",
    "            else:\n",
    "                continue\n",
    "        return b_i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 动态规划+堆（优先队列）\n",
    "    def maxBoxesInWarehouse(self, boxes: List[int], warehouse: List[int]) -> int:\n",
    "\n",
    "        n = len(warehouse)\n",
    "        right = [0] * n\n",
    "        ceil = float(\"inf\")\n",
    "        for i in range(n-1, -1, -1):\n",
    "            ceil = warehouse[i] if warehouse[i] < ceil else ceil\n",
    "            right[i] = ceil\n",
    "\n",
    "        left = [0] * n\n",
    "        ceil = float(\"inf\")\n",
    "        for i in range(n):\n",
    "            ceil = warehouse[i] if warehouse[i] < ceil else ceil\n",
    "            left[i] = ceil\n",
    "\n",
    "        heapq.heapify(boxes)\n",
    "        stack = [max(left[i], right[i]) for i in range(n)]\n",
    "        heapq.heapify(stack)\n",
    "        ans = 0\n",
    "        while boxes and stack:\n",
    "            x = heapq.heappop(boxes)\n",
    "            while stack and stack[0] < x:\n",
    "                heapq.heappop(stack)\n",
    "\n",
    "            if stack:\n",
    "                ans += 1\n",
    "                heapq.heappop(stack)\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxBoxesInWarehouse(self, boxes: List[int], warehouse: List[int]) -> int:\n",
    "        n = len(warehouse)\n",
    "        left = [0] * n\n",
    "        ceil = inf\n",
    "        for i in range(n):\n",
    "            ceil = warehouse[i] if warehouse[i] < ceil else ceil\n",
    "            left[i] = ceil\n",
    "        right = [0] * n\n",
    "        ceil = inf\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            ceil = warehouse[i] if warehouse[i] < ceil else ceil\n",
    "            right[i] = ceil\n",
    "        stack = [max(left[i], right[i]) for i in range(n)]\n",
    "        heapq.heapify(stack)\n",
    "        heapq.heapify(boxes)\n",
    "        ans = 0\n",
    "        while boxes and stack:\n",
    "            x = heapq.heappop(boxes)\n",
    "            while stack and stack[0] < x:\n",
    "                heapq.heappop(stack)\n",
    "            if stack:\n",
    "                ans += 1\n",
    "                heapq.heappop(stack)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxBoxesInWarehouse(self, boxes: List[int], warehouse: List[int]) -> int:\n",
    "        n = len(warehouse)\n",
    "        ans = 0\n",
    "        left = [0] * n\n",
    "        ceil = inf\n",
    "        for i in range(n):\n",
    "            ceil = min(ceil, warehouse[i])\n",
    "            left[i] = ceil\n",
    "        right = [0] * n\n",
    "        ceil = inf\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            ceil = min(ceil, warehouse[i])\n",
    "            right[i] = ceil\n",
    "        stack = [max(left[i], right[i]) for i in range(n)]\n",
    "        heapify(stack)\n",
    "        heapify(boxes)\n",
    "        while stack and boxes:\n",
    "            x = heappop(boxes)\n",
    "            while stack and stack[0] < x:\n",
    "                heappop(stack)\n",
    "            if stack:\n",
    "                ans += 1\n",
    "                heappop(stack)\n",
    "        return ans\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
